
void merge(int *data, int *data_tmp, int start_index, int mid_index, int end_index)
{	
	int i = start_index;
	int j = mid_index;
	int k = start_index;

	while (i < mid_index && j <= end_index )
	{
		if (data[i] <= data[j])
		{
			data_tmp[k] = data[i];
			k++;
			i++;
		}
		else
		{
			data_tmp[k] = data[j];
			k++;
			j++;
		}
	}
	while (i < mid_index)
	{
		data_tmp[k] = data[i];
		k++;
		i++;
	}
	while (j <= end_index)
	{
		data_tmp[k] = data[j];
		k++;
		j++;
	}

}


int merge_sort(int *data, int data_lenth)
{
	if (data == 0 || data_lenth <= 0)
	{
		return -1;
	}

	int gap = 0;
	int i = 0;
	int end = 0;
	int step = 0;
	int is_in_data = 1;
	int *data_tmp = malloc(data_lenth*sizeof(int));

	
	/** 以gap 为间隔 分割 为若干个子序列 **/
	for (gap = 1; gap<data_lenth; gap *= 2)
	{
		step = 2*gap;
		end = data_lenth - step;
		for ( i = 0; i < end; i += step)
		{
			if (is_in_data)
				merge(data, data_tmp, i, i + gap, i + step - 1);
			else
				merge(data_tmp, data, i, i + gap, i + step - 1);
		}

		if ( i < data_lenth - gap)
		{
			if (is_in_data)
				merge(data, data_tmp, i, i + gap, data_lenth - 1);
			else
				merge(data_tmp, data, i, i + gap, data_lenth - 1);

			i += step;
		}

		if ( i < data_lenth )
		{
			if (is_in_data)
				merge(data, data_tmp, i, i, data_lenth - 1);
			else
				merge(data_tmp, data, i, i, data_lenth - 1);

			i += step;
		}
		is_in_data = !is_in_data;
	}
	if (!is_in_data)
	{
		memcpy(data, data_tmp, data_lenth*sizeof(int));
	}
	free(data_tmp);
	
}
